package 简单.动态规划.斐波那契数列;

/**
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * <p>
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * <p>
 * 注意：给定 n 是一个正整数。
 * <p>
 * 四步走：
 * 1，定义子问题(分析开头特殊情况的值)
 * 爬到第k个的台阶有多少方法。
 * 爬到第0个台阶有1种方法
 * 爬到第1个台阶有1种方法
 * 2，写出子问题的递推关系
 * 爬到第k个台阶有两种方法，从k-1或者k-2的台阶过来，所有爬到f(k)个台阶的方法由
 * 爬到第f(k-1)+f(k-2)的台阶方法相加。
 * f(k)=f(k-1)+f(k-2)
 * 3，确定DP数组的计算顺序
 * 从首到尾
 * 4，空间优化
 * 因为第K个值只与前面两个值有关，所以定义两个变量记录就行。
 * <p>
 * 题目变形：
 * 1、每次你可以爬 1 或 2 个台阶。 2、不能连续跳两个台阶。（这次跳了两个台阶，下次不能再跳两个台阶）
 * dp[i]=dp[i-1]+dp[i-3]
 * <p>
 * 来源：https://leetcode-cn.com/problems/climbing-stairs/
 */

public class 爬楼梯_70 {

    public static void main(String[] args) {

        int i = efficientClimbStairs(7);
        System.out.println(i);

    }

    //常规动态规划
    public static int climbStairs(int n) {
        // 防止数组溢出（f[1]）
        int[] dp = new int[n + 2];
        //初始化边界值
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        if (n < 3) return dp[n];
        //第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    //空间复杂度优化
    public static int efficientClimbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        //前2，1个位置的值
        int pre2 = 1, pre1 = 2;
        for (int i = 2; i < n; i++) {
            int cur = pre1 + pre2;
            //步进1个位置
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }

    //变种题:1、每次你可以爬 1 或 2 个台阶。 2、不能连续跳两个台阶。（这次跳了两个台阶，下次不能再跳两个台阶）
    public static int efficientClimbStairs2(int n) {
        //开头情况分析,(0):1 - (1):1 - (2):2 - 3:(0)+(2)=3 - 4:(1)+(3)=4
        if (0 == n) {
            return 1;
        } else if (n <= 2) {
            return n;
        }
        //(0):1 - (1):1 - (2):2
        int pre3 = 1, pre2 = 1, pre1 = 2;
        for (int i = 3; i <= n; i++) {
            //dp[i]=dp[i-1]+dp[i-3]
            int cur = pre1 + pre3;
            pre3 = pre2;
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }


}
